import java.util.Arrays;
import java.util.Stack;

public class LeetCode105 {
    /*
        preOrder = {1,2,4,3,6,7}//前序遍历
        inOrder = {4,2,1,6,3,7}//中序遍历

        前序遍历 确定根
        中序遍历 确定左右子树
        根 1
            pre         in
        左  2,4         4,2
        右  3,6,7       6,3,7


        根 2
        左 4

        根 3
        左 6
        右 7
     */
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || preorder.length == 0 || inorder == null || inorder.length == 0) {
            return null;
        }
        //创建根节点
        int rootValue = preorder[0];
        TreeNode root = new TreeNode(rootValue);
        //区分左右子树
        for (int i = 0; i < inorder.length; i++) {
            if (inorder[i] == rootValue) {
                //左子树  0 ~ i - 1
                int[] inLeft = Arrays.copyOfRange(inorder, 0, i);//区间复制数组
                //右子树 ：i + 1 ~ inOrder.length - 1
                int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length);

                int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1);
                int[] preRight = Arrays.copyOfRange(preorder, i + 1, preorder.length);

                root.left = buildTree(preLeft, inLeft);
                root.right = buildTree(preRight, inRight);
                break;
            }
        }
        return root;
    }
}
